#include<bits/stdc++.h>
using namespace std;
const long long maxn=10005;
long long T;
long long n,m;
long long s[maxn*10];
long long dp[maxn][maxn];
long long ans;
int main(){
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    scanf("%lld",&T);
    while(T--){
        ans=0;
        scanf("%lld",&n);
        for(long long i=1;i<=n;i++){
            scanf("%lld",&s[i]);
        }
        if(n>maxn){
            for(long long i=1;i<=n;i++)
                ans+=s[i];
            printf("%lld\n",ans/2);
            continue;
        }
        for(long long i=0;i<n+3;i++)
            for(long long j=0;j<n+3;j++)
                dp[i][j]=0;
        for(long long i=1;i<=n;i++){
            for(long long j=1;j<=n;j++){
                dp[max(i,j)+1][j]=max(dp[max(i,j)+1][j],dp[i][j]+(long long)((s[max(i,j)+1]==s[i])?s[i]:0));
                dp[i][max(i,j)+1]=max(dp[i][max(i,j)+1],dp[i][j]+(long long)((s[max(i,j)+1]==s[j])?s[j]:0));
            }
        }
        for(long long i=0;i<n;i++)ans=max(ans,max(dp[i][n],dp[n][i]));
        printf("%lld\n",ans);
    }
}